package leetcode46

// 解答失败: 测试用例:[5,4,6,2] 测试结果:
//[[5,4,2,6],[5,4,2,6],[5,6,2,4],[5,6,2,4],[5,2,6,4],[5,2,6,4],[4,5,2,6],[4,5,2,6],[4,6,2,5],[4,6,2,5],[4,2,6,5],[4,2,6,5],[6,5,2,4],[6,5,2,4],[6,4,2,5],[6,4,2,5],[6,2,4,5],[6,2,4,5],[2,5,6,4],[2,5,6,4],[2,4,6,5],[2,4,6,5],[2,6,4,5],[2,6,4,5]]
//[[5,4,6,2],[5,4,2,6],[5,6,4,2],[5,6,2,4],[5,2,4,6],[5,2,6,4],[4,5,6,2],[4,5,2,6],[4,6,5,2],[4,6,2,5],[4,2,5,6],[4,2,6,5],[6,5,4,2],[6,5,2,4],[6,4,5,2],[6,4,2,5],[6,2,5,4],[6,2,4,5],[2,5,4,6],[2,5,6,4],[2,4,5,6],[2,4,6,5],[2,6,5,4],[2,6,4,5]] stdout:

func permute(nums []int) [][]int {
	var (
		res    = make([][]int, 0)
		path   []int
		length = len(nums)
		used   = make(map[int]bool, length)
	)
	if length == 0 {
		return res
	} else if length == 1 {
		return append(res, nums)
	}
	dsf(nums, 0, length, path, used, &res)
	return res
}

func dsf(nums []int, depth int, length int, path []int, used map[int]bool, res *[][]int) {
	if depth == length {
		// 为何原来失败
		temp := make([]int, len(path), len(path))
		copy(temp, path)
		*res = append(*res, temp)
		return
	}
	for _, num := range nums {
		if used[num] {
			continue
		}
		path = append(path, num)
		used[num] = true
		dsf(nums, depth+1, length, path, used, res)
		used[num] = false
		path = path[:len(path)-1]
	}
}
